#ifndef __CDS__RBTREE_H__
#define __CDS__RBTREE_H__
#include<stdio.h>
#include<assert.h>
#include "cds_common.h"

#ifdef __cplusplus
extern "C"{
#endif

/*
 * 红黑树的性质:
 *  1, 每一个节点或着红色或着黑色
 *  2, 根节点是黑色
 *  3, 如果一个节点是红色的，那么它的子节点必须是黑色的
 *  4, 从一个节点到一个NULL指针的每一条路径必须包含相同数量的黑色节点
 *  5, NULL节点当作黑色节点
 * 
 *  通俗的理解:
 *      红黑树的平衡是只统计路径上的黑色节点的数量,
 *      红色节点间隔地插在黑色与黑色之间，且一个路径上
 *      的两个黑色节点之间不能连续插两个红色,所以路径长度之差最大是2倍关系,基本平衡
 *
 */
//红黑树节点
struct rb_node {
    unsigned long parent_color; 
    struct rb_node *left,*right; 
} __attribute__((aligned(sizeof(long)))) ;

typedef struct rb_node rbnode_t;

typedef unsigned long (*keygen_func_t)(rbnode_t * node);

typedef void (*travel_func_t)(rbnode_t * node);

typedef void (*destroy_func_t)(rbnode_t * node);

//红黑树
struct rb_tree {
    rbnode_t * root;
    unsigned long size;
    keygen_func_t keygen_func;
};

typedef struct rb_tree rbtree_t;

//初始化红黑树指针
#define RBTREE_INIT(tree, func) do{\
    tree->root = NULL;\
    tree->size = 0;\
    tree->keygen_func = func;\
    assert(func);\
}while(0)

//给红黑树变量赋的初始值
#define RBTREE(func) ({\
    assert(func);\
    ((rbtree_t){NULL,0,func});\
    })

//获取包含rbnode_t类型成员member的type类型的数据结构地址
#define rbtree_entry( ptr, type, member ) \
    container_of(ptr,type,member)

//获取红黑树中节点数量
#define rbtree_size(tree) ((tree)->size)

//遍历红黑树
#define rbtree_for_each(pos,tree) \
    for(pos = rbtree_first(tree->root);\
        pos; pos=rbtree_next(pos) )
//树中最小节点
#define rbtree_first(root) ({\
    rbnode_t * _root = (root);\
    while(_root->left) _root = _root->left;\
    _root;})
//树中最大节点
#define rbtree_last(root) ({\
    rbnode_t * _root = (root);\
    while(_root->right) _root = _root->right;\
    _root; })

//下一个节点
rbnode_t * rbtree_next(rbnode_t * node );
//上一个节点
rbnode_t * rbtree_prev(rbnode_t * node );
//删除
void rbtree_del(rbtree_t * tree, rbnode_t * node );
//插入
rbnode_t * rbtree_insert(rbtree_t * tree, rbnode_t * node );
//搜索
rbnode_t * rbtree_search(rbtree_t * tree, unsigned long key );
//层次遍历
void rbtree_travel_level(rbtree_t * tree, travel_func_t travel );
//中序遍历 
void rbtree_travel_middle(rbtree_t * tree, travel_func_t travel);
//清空
void rbtree_clear(rbtree_t * tree, destroy_func_t destroy );
//检测平衡函数
void rbtree_check_balance(rbtree_t * tree);
#ifdef __cplusplus
}
#endif
#endif //__CDS__RBTREE_H__
